The present invention generally relates to data processing with microprocessors. More specifically, the invention relates to processing data located in an array of storage elements.
Packet-based switching has been the focus of many telecommunication providers and manufacturers for some years now (ATM is a form of packet switching as used herein). At each network point in a packet-switched network, the communicated data may be processed for several reasons, such as error handling, traffic management, routing, etc. Generally, each packet, or Protocol Data Unit (PDU), may include some overhead, typically present in header and trailer fields, along with the relevant communicated data in a payload. The header of the PDU may include the appropriate information that a network point may need to perform the various functions listed above.
As the quest for speed continues to drive the networking and telecommunication industries, the equipment at the network points is expected to perform at faster speeds. For these reasons, hardware vendors are turning to network processors (also called communications processors) to support increasingly complex tasks at wire speeds. Programmable network processors can provide system flexibility while delivering the high-performance hardware functions required to process the PDUs at wire speed.
Generally, network processors perform four general tasks: parse, search, resolve, and modify. Network-specific processors strive to optimize each of these tasks to boost the processing performance. FIG. 1 illustrates a method 10 for processing data at a network point, such as at a packet switch, that is generally well known in the art. The first step 1 is to receive the data at the physical layer. Generally, this step may require the data to be converted from analog to digital, if necessary. Next, the digital data may be buffered into a temporary storage location (step 2). Typically, the buffer will be a Random Access Memory (RAM), or a register . In general, though, the buffer may be some type of fast memory location. Once buffered, the network processor can begin working on the data.
The first step generally performed by the network processor is to parse the PDU (step 3). In essence, parsing involves analyzing and classifying the contents of the PDU and its fields. Once parsed, appropriate fields of the PDU may be used to search tables for matches (step 4). The tables may be routing tables that dictate the next destination for the packet. Just prior to, or just after searching, error handling may be performed, commonly with a cyclic redundancy check (CRC), to verify if the PDU is valid. The next step is to resolve the destination and Quality of Service (QoS) requirements (step 5). Certain packets may be given certain priority, re-routing information may need to be determined and communicated, etc. When necessary, the PDU may be modified and/or updated with the appropriate routing information (step 6). Once the PDU has been updated, the packet may be sent to its next destination through the network (step 7).
In terms of speed, processors are typically measured by the number of clock cycles necessary to perform a particular task combined with their clock frequency. For embedded applications, the energy efficiency is also an important performance parameter. Several algorithms are known in the art that perform the parsing and modifying of the PDU""s. Each algorithm varies in complexity as well as performance, e.g. required clock cycles. For example, a relatively straightforward approach to parsing can be performed in software with a higher level programming language such as C. A simple record structure that is made up of several fields may be used to represent a PDU. Each field of the PDU record may be directly addressed which allows for easy access and manipulation of the fields. Unfortunately, while not complex, the programmer can not model the method in which the data is accessed in memory. Quite often, many wasteful clock cycles are used when a software approach is utilized, which leads to poor performance.
Other software solutions can utilize manual bit-level operations. A well known scheme that is often utilized by general purpose processors is a shift and mask operation. In general, to access a field located in a PDU, the field may need to be shifted so that the least-significant-bit (Isb) of the field is the lsb of the current register. The other remaining, unimportant bits in the register, can then be masked out. This, although typically more efficient than the previous solution, can still be quite cumbersome.
Hardware solutions have also been created to parse and modify a given PDU. Most of these solutions simply mirror the software implementations above. Other solutions simply consist of hardwired state machines.
Therefore, there exists a need for improved systems and methods for processing data that is stored in a packed structure, such as a PDU. It would be desirable for this solution to require as little clock cycles as necessary, but still allow for flexibility in design and implementation.
The present invention relates to methods and systems for processing data, particularly data of a packed data structure, such as a PDU. In this regard, an embodiment of a system for parsing data stored in an array of storage elements includes a decoder configured to receive a desired register format from a plurality of register formats and further configured to activate an enable signal from a set of enable signals based on the desired register format. The system also includes operational logic configured to derive an array of output data bits related to the desired register format. The operational logic receives as inputs the set of enable signals and selectively connected storage elements of the array of storage elements.
In another embodiment, a system for writing data to an array of storage elements includes a decoder configured to receive a desired register format from a plurality of register formats and further configured to activate an enable signal from a set of enable signals based on the desired register format. The system also includes an array of bit-selector blocks configured to write the data to the array of storage elements in the desired register format. Each bit-selector block receives as inputs various selected bits of the data and selected enable signals of the set of enable signals, such that activation of one of the selected enable signals dictates which bit of the various input bits is to be written to a particular storage element.
Another embodiment may be construed as a system for parsing and modifying data stored in an array of storage elements. This system includes a read decoder configured to receive a desired register format from a plurality of register formats and further configured to activate a read-enable signal from a set of read-enable signals based on the desired register format. The system also includes operational logic configured to derive an array of output data bits related to the desired register format, wherein the operational logic receives as inputs the set of read-enable signals and selectively connected storage elements of the array of storage elements. The system further includes a write decoder configured to receive a desired register format from the plurality of register formats and further configured to activate a write-enable signal from a set of write-enable signals based on the desired register format and an array of bit-selector blocks configured to write the data to the array of storage elements in the desired register format. Each bit-selector block receives as inputs various selected bits of the data and selected write-enable signals of the set of write-enable signals, such that activation of one of the selected write-enable signals dictates which bit of the various input bits is to be written to a particular storage element.
Another embodiment may be construed as a system for parsing data stored in an array of storage elements. The system includes a Read Programmable Table (RPT) preprogrammed with bit-level mapping information related to the array of storage elements and a read selector block coupled to the RPT and configured to, when enabled, read and output contents of appropriately selected storage elements of the array of storage elements based upon the bit-level mapping information provided by the RPT.
Yet another embodiment may be construed as a system for writing data to an array of storage elements. The system includes a Write Programmable Table (WPT) preprogrammed with bit-level mapping information related to the array of storage elements and a write selector block coupled to the WPT and configured to, when enabled, write selected bits of the data to particular storage elements of the array of storage elements based upon the bit-level mapping information provided by the WPT.
In another embodiment, a system for parsing and modifying data stored in an array of storage elements includes a parsing system configured to access the data stored in selected storage elements of the array of storage elements and output the data in one of a plurality of register formats and a write system configured to write data to selected storage elements of the array of storage elements, wherein the data is received in one of the plurality of register formats. The plurality of register formats includes a first set of register formats corresponding to a packed representation of the data and a second set of register formats corresponding to an unpacked representation of the data.
Another embodiment may be construed as a system for parsing and modifying data stored in an array of storage elements This system includes means for receiving a desired parsing format of a plurality of register formats, wherein the data is to be output in the desired parsing format, means for determining which storage element is to be accessed for each bit of the desired parsing format; and means for outputting the data in the desired parsing format. The plurality of register formats includes a first set of register formats corresponding to a packed representation of the data and a second set of register formats corresponding to an unpacked representation of the data.
In another embodiment, a representative method for parsing and modifying data stored in an array of storage elements includes: receiving a desired parsing format of a plurality of register formats, wherein the data is to be output in the desired parsing format; determining which storage element is to be accessed for each bit of the desired parsing format; and outputting the data in the desired parsing format. The plurality of register formats includes a first set of register formats corresponding to a packed representation of the data and a second set of register formats corresponding to an unpacked representation of the data.